package leetcode.BinarySearch;

public class MySqrt {
    public static int mySqrt(int x) {

        long start = 0;
        long end = x;


        while (end >= start) {
            long mid = start + (end - start) / 2;
            if (mid * mid == x) {
                return (int)mid;
            } else if (mid * mid < x && (mid + 1) * (mid + 1) > x) {
                return (int)mid;
            } else if (mid * mid < x) {
                start = mid + 1;
            } else {
                end = mid - 1;

            }
        }
        return -1;

    }

    public int betterMySqrt(int x) {
        if(x==0)return 0;
        long i=x;
        while(i>x/i){
            i=(i+x/i)/2;
        }
        return (int)i;
    }

    public static void main(String[] args) {
        System.out.println(mySqrt(2147395599));
        System.out.println(2147395599l*2147395599l);

    }
}
